package com.cat.dataStructure02;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-of-integers/
 * @create 2025/10/29 16:45
 * @since JDK17
 */

public class Solution79 {
    static int N = ((int) (1e9 + 7));
    static int max, min, len;
    static int[][][] dp = new int[23][401][2];
    static char[] arr;
    int f(int i, int sum, int free) {
        if (sum > max || (len - i) * 9 + sum < min) {
            return 0;
        }
        if (i == len) {
            return 1;
        }
        if (dp[i][sum][free] != -1) {
            return dp[i][sum][free];
        }
        int ans = 0, end = arr[i] - '0';
        if (free == 0) {    //
            for (int j = 0; j < end; j++) {
                ans += f(i + 1, sum + j, 1);
            }
            ans += f(i + 1, sum + end, 0);
        } else {
            for (int j = 0; j <= end; j++) {
                ans += f(i + 1, sum + j, 1);
            }
        }

        return dp[i][sum][free] = ans;
    }
    void clear() {
        for (var x : dp) {
            for (var y : dp) {
                Arrays.fill(y, -1);
            }
        }
    }
    boolean check(char[] arr) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            ans += arr[i] - '0';
        }
        return ans >= min && ans <= max;
    }

    public int count(String num1, String num2, int min_sum, int max_sum) {
        max  = max_sum;
        min = min_sum;
        arr = num2.toCharArray();
        len = arr.length;
        int ans = f(0, 0, 0);
        clear();
        arr = num1.toCharArray();
        len = arr.length;
        ans = (ans - f(0, 0, 0) + N) % N;
        if (check(arr)) {
            ans = (ans + 1) % N;
        }
        return ans;
    }
}
